home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / isoc / pub / isoc_news / 2-3 / Partridge, Craig - Parallel Processors and Gigabit Networks.Z / Partridge, Craig - Parallel Processors and Gigabit Networks
Text File  |  1994-03-20  |  6KB  |  105 lines
  1. N-2-2-030.50.2
  2.  
  3. Parallel Processors and Gigabit Networks
  4. by Craig Partridge
  5. <craig@aland.bbn.com>
  6.  
  7.     Computers that use multiple processors are becoming an increasingly
  8. important part of the computing milieu.  Most supercomputers today use
  9. multiple processors in parallel, and the technology is rapidly moving into
  10. workstations and PCs.  As a result, it seems inevitable that attaching
  11. parallel processors to gigabit networks is a a problem we will need to
  12. solve.  This quarter's column takes a look at some of what is currently
  13. known about parallel processing of network protocols.
  14.  
  15.     It is important to recognize that parallel processing of network
  16. protocols is a hard problem.  An example illustrates the point.  A major
  17. supercomputing company took some care about a year ago to develop what they
  18. thought would be a high quality TCP/IP implementation for their multiprocessor.
  19. But when they tested its performance they discovered that it could handle only
  20. a few thousand TCP/IP datagrams per second! (That's about what a good PC can
  21. handle).  There are a lot of potential bottlenecks in parallel processing
  22. of protocols, and this implementation had hit a couple of them.  In the
  23. next few paragraphs we'll examine some of the major problems and their
  24. solutions (if known).
  25.  
  26.     The most important major bottleneck can be described as the
  27. serial-to-parallel problem.  In brief, the problem that there's a single
  28. network interface into the parallel computer and that something in the system
  29. has to coordinate moving data from a single interface to multiple processors
  30. (or from multiple processors to a single interface).  The coordinating
  31. something is typically a single processor, which inevitably means that
  32. the multiprocessor system's packet processing rate is bounded by the
  33. maximum rate that a single one of its processors can move packets on
  34. and off the network.  Complicating this problem is the fact that on many
  35. parallel processing machines, a single application may be running in parallel
  36. on several processors.  So a single TCP segment may contain data destined
  37. for several different processors - in some implementations, the poor
  38. processor managing the interface often has to parse the TCP segment
  39. to figure out which processors get which pieces of the data.  There
  40. are at least two ways people are trying to handle this problem.
  41.  
  42.     One approach is to put multiple network interfaces into the parallel
  43. processor.  Data for a particular application, or piece of an application, is
  44. sent to the network interface closest to the processors on which that
  45. application is running.  By properly balancing networked applications across
  46. the processors and interfaces, there's a good chance of achieving high
  47. performance.  Experiments using this approach (as part of a broader study
  48. of networking with parallel processors) are currently underway using
  49. ATM network interfaces and Thinking Machines computers at the US Naval
  50. Research Laboratory.
  51.  
  52.     Another approach is to try to minimize the work that the processor
  53. managing the interface must do.  A popular idea is to simply the processor
  54. move packets on and off the network, and move all the protocol processing to
  55. a group of processors inside the system.  (Note that this approach is
  56. complimentary to the multiple interface approach, and so they can both
  57. be used).  The major puzzle in this approach is figuring out how best
  58. to process packets in parallel within a group of processors.
  59.  
  60.     There are at least four known methods for parallel packet processing.
  61. The first method is to assign a processor to each logical connection, which
  62. handles all packets for that connection.  The major disadvantage of this
  63. method is that even a connection that needs high throughput is limited
  64. by the capacity of a single processor.
  65.  
  66.     The second method is assign a processor to each network protocol (e.g.,
  67. one processor for IP, one for TCP, one for UDP).  Packets move from 
  68. processor to processor for protocol processing.  Some of the problems with
  69. this approach are that throughput is limited by the slowest protocol in
  70. pipeline, and hopping from one processor to another is expensive in some
  71. multiprocessors.
  72.  
  73.     The third method is to assign a processor to individual protocol
  74. subfunctions.  So one processor might compute the TCP checksum, while another
  75. does TCP sequencing and a third does round-trip time estimation.  The major
  76. problem with this approach is that the cost of splitting pieces of the packet
  77. (and related state like TCP protocol control blocks) across multiple processors
  78. is typically far expensive than the cost of processing the TCP segment itself
  79. (which is only about 100 instructions).
  80.  
  81.     The fourth (and to my mind, most promising) method is to assign a different
  82. processor to each packet that comes in, and have the processor do all the
  83. protocol processing on that packet.  This method largely addresses the
  84. problems in the other three (a single connection can use multiple processors,
  85. slow protocols don't affect other packets as much, and we don't have to split
  86. packets across processors).  The main performance barrier is the occasional
  87. need to share state.  For example, if two TCP segments for the same connection
  88. are being handled on two different processors, the processors need to
  89. coordinate their access to the TCP protocol control block to avoid corrupting
  90. the TCP state information.  Work on this problem is being done at the
  91. Swedish Institute of Computer Science.
  92.  
  93.     Finally, one of the key problems in multiprocessors is that most
  94. multiprocessors are built using regular processor chips like those in
  95. workstations and PCs.  And as earlier columns have explained, the networking
  96. community is still working hard on making uniprocessor implementations on those
  97. processors run fast.  So the people working on parallel processing actually
  98. have a dual problem: first they have to make sure that their implementation
  99. is well-tuned for their processors, and then they have to figure out how
  100. to make the implementation run well in parallel.  So there are lots of
  101. challenges in this area.
  102.  
  103. References: For a good survey of the work on parallel packet processing, see
  104. the paper by Bjorkman and Gunningberg in the Proceedings of ACM SIGCOMM '94.
  105.